package num;

/**
 * @program: data_structures_algorithms
 * @description: 输入n，输出0-最大n位数
 * @author: lld
 * @create: 2021-04-14 16:52
 **/
class BigNumPrint {
    char[] num;
    int n;//位数，在dfs方法需要使用
    StringBuilder sb;
    char[] loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
//    删除前面的0
    int start;
    int nine=0;
    public String printNumbers(int n) {
        this.n = n;//在dfs方法需要使用,需要在这里赋值
        sb = new StringBuilder();
        num = new char[n];
//        dfs(0);
        start=n-1;
        dfs2(0);
//        删除最后一个 ,
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();

    }

    /**
     * @Description: 不删除首部的0
     **/
    private void dfs(int index) {
//       递归的中止条件为已经生成了digit位的数字
        if (index == n) {
            sb.append(String.valueOf(num)).append(",");
            return;
        }
        for (char c : loop) {
            num[index] = c;
            dfs(index + 1);
        }

    }
    /**
     * @Description: 不删除首部的0
     * 1. 删除高位多余的 00 ：
     * 字符串左边界定义： 声明变量 start 规定字符串的左边界，以保证添加的数字字符串 num[start:] 中无高位多余的 00 。
     * 例如当 n = 2n=2 时， 1 - 91−9 时 start = 1start=1 ， 10 - 9910−99 时 start = 0start=0 。
     *
     * 左边界 start 变化规律： 观察可知，当输出数字的所有位都是 99 时，则下个数字需要向更高位进 11 ，
     * 此时左边界 start 需要减 11 （即高位多余的 00 减少一个）。例如当 n = 3n=3 （数字范围 1 - 9991−999 ）时，
     * 左边界 start 需要减 11 的情况有： "009" 进位至 "010" ， "099" 进位至 "100" 。设数字各位中 99 的数量为 nine ，
     * 所有位都为 99 的判断条件可用以下公式表示：
     *
     * n - start = nine
     * n−start=nine
     *
     * 统计 nine 的方法： 固定第 xx 位时，当 i = 9i=9 则执行 nine = nine + 1 ，
     * 并在回溯前恢复 nine = nine - 1 。
     *
     **/
    private void dfs2(int index) {
//       递归的中止条件为已经生成了digit位的数字
        if (index == n) {
            String s = String.valueOf(num).substring(start);
            if(!s.equals("0")) sb.append(s).append(",");
            if(n-start==nine) start--;
            return;
        }
        for (char c : loop) {
            if(c == '9') nine++;
            num[index] = c;
            dfs2(index + 1);
        }
        nine--;

    }

    public static void main(String[] args) {
        BigNumPrint bigNumPrint = new BigNumPrint();
        String s = bigNumPrint.printNumbers(2);
        System.out.println(s);
    }
}